package ljl.alg.jianzhioffer.round3.easy;

import commons.TreeNode;

public class _55_isBalanced {

    class normal {
        public boolean isBalanced(TreeNode root) {
            if (root == null)
                return true;
            return isBalanced(root.left)
                    && isBalanced(root.right)
                    && Math.abs(height(root.left) - height(root.right)) < 2;
        }

        int height(TreeNode node) {
            return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
        }
    }

    class lufei {
        public boolean isBalanced(TreeNode root) {
            return height(root) > -1;
        }

        private int height(TreeNode node) {
            if (node == null)
                return 0;
            int l = height(node.left);
            if (l == -1)
                return -1;
            int r = height(node.right);
            if (r == -1)
                return -1;
            if (Math.abs(l - r) > 1)
                return -1;
            return Math.max(l , r) + 1;
        }
    }
}
